The present invention relates to a demodulation method and apparatus for use in demodulating convolutional codes and Trellis coded modulation (TCM) signal, and more particularly to a decoding method and apparatus having an optimum decoding path in which received data is decoded using an overlapped Viterbi decoder and the decoded data is output.
In general digital communications, a signal transmitted from a transmission portion is changed into another signal different from the original signal due to influence of noise imposed on channels, and the changed signal is received by a reception portion. To reduce errors generated in the signal, the digital communication uses an error correcting method to reduce errors generated in the transmission line. Channel encoding methods using a Reed-Solomon code, a convolutional code, etc., are known. The convolutional code is strong with respect to a random error. A maximum likelihood decoding method proposed by Viterbi is chiefly used as a method of decoding the convolutional code.
FIG. 1 is a block diagram of one example of a convolutional encoder.
The FIG. 1 apparatus is an encoder which uses (2,1,2) convolutional code. The encoder includes a first delay 11 which receives bit data D.sub.IN input from an external information source and stores the input bit data, and simultaneously outputs the previously stored bit data. The output of first delay 11 is connected to a second delay 12 which stores the data supplied from first delay 11 and simultaneously outputs the previously stored bit dam. Also, the appratus includes a first exclusive-OR (XOR) gate 13 for exclusive-ORing the the bit data D.sub.IN and the data serially output from first and second delays 11, 12, and a second XOR gate 14 for exclusive-ORing the bit data D.sub.IN the bit data supplied from first delay 11 and the bit data serially output from first and second delays 11 and 12. The outputs from first and second XOR gates 13 and 14 are supplied to a switching portion 15 which sequentially transmits the data received from first and second XOR gates 13 and 14 as 2-bit data.
In FIG. 1, it is assumed that initial states of first and second delays 11 and 12 are "0" and "0, " respectively, and the bit data input from the external information source is "1", "0", "1", "1", and "1". At first, a first bit "1" of the bit data is supplied to first delay 11 and first and second XOR gates 13 and 14, respectively. First delay 11 stores the input data "1" and simultaneously supplies the previously stored data "0" to second delay 12 and second XOR gate 14, respectively. Second delay 12 receives the data "0" supplied from first delay 11 and stores the received data, and supplies the stored data "0" to first and second XOR gates 13 and 14. Thus, first delay 11 stores the bit data "1", and second delay 12 stores the bit data "0". As a result, when the bit data "1" is input to first delay 11, both first and second XOR gates 13 and 14 output the bit data "1". Then, switching portion 15 outputs the input data sequentially in such a manner that the bit data supplied from first XOR gate 13 is outputted and then the bit data supplied from second XOR gate 14 is outputted. By repetitively performing the above procedure, the outputs D.sub.OUT of the convolutional encoder and the states of delays 11 and 12 are obtained as in the following Table 1.
TABLE 1 ______________________________________ STATE OF INPUT DELAYS OUTPUT STEP (D.sub.IN) 11 12 (D.sub.OUT) ______________________________________ INITIAL 0 0 1 1 1 0 1 1 2 0 0 1 0 1 3 1 1 0 0 0 4 1 1 1 1 0 5 1 1 1 0 1 6 0 0 1 1 0 7 0 0 0 1 1 ______________________________________
Here, although the total input data is 5-bit data, the output is not 10-bit data but 14-bit data. The reason is because 2-bit null data of "0" and "0" have been input for the purpose of outputting the remaining data in delays 11 and 12 after outputting the 10-bit data. This null data plays a role of converging the final state into the initial state of "0" and "0" in Trellis diagram of Viterbi decoding to be explained later on referring to FIG. 2. The characteristic of the convolutional code is in that the past input information has influence upon the encoding of the currently input information due to the delays included in the encoder. The maximum likelihood decoding method by the Viterbi algorithm is very often used in the decoding of the convolutional codes due to the correlation between the previously encoded information and the currently encoded information. The maximum likelihood decoding method makes up the Trellis diagram with respect to the encoding data as much as possible, and calculates a Hamming distance of each node with respect to the data input to the decoder in the Trellis diagram. Then, in the maximum likelihood decoding method, the Hamming distance is accumulated with respect to all possible paths, and only a path having the shortest accumulated Hamming distance is left as a survival path. The finally existing survival path becomes a decoding path with respect to all the input data.
Although such a survival path determination technology is known, it will be briefly described below using the Trellis diagram of (2,1,2) convolutional code shown in FIG. 2.
FIG. 2 is a Trellis diagram for explaining the decoding of the data which is encoded by the FIG. 1 apparatus. In FIG. 2, the node of each step has two paths. A "higher path" which is located in a relatively higher position is made when the input of the encoder is "0," and a "lower path" which is located in a relatively lower position is made when the input of the encoder is "1". Also, two bits on each path represent the output of the encoder with respect to each input, that is, the input of the decoder. When the 2-bit error is generated in the output D.sub.OUT which is encoded in the FIG. 1 encoder and the 2-bit error is input to the decoder, the decoder corrects the error of the input signal and restores the input signal into an original signal. The bits represented in a symbol "x" among the received data ##EQU1## are the error-generated bits. The decoding procedure of the error-generated data is as follows.
At the initial step (step 0 of FIG. 2), if the data "11" is input to the decoder, the Hamminig distance to the 2-bit reference data on each path, that is, the number of the corresponding bits different from each other is obtained and stored in each node of the first step. In the same manner, the Hamming distance which is calculated with respect to the secondly input data "11" is added to the previously obtained Hamming distance and the summed Hammining distance is stored in each node of the second step. By repetitively performing such a process, a plurality of paths may be input to one node at a certain moment. In this case, the path having the shortest accumulated Hamming distance is left as a survival path among various paths, and the remaining paths are ignored. If such a process is repetitively performed, only one survival path is left at the final step. The one-bit data which is determined according as the path direction between the respective nodes forming the survival path is upward or downward and forms the decoded data. The portion which is shown in a heavy solid line in FIG. 2 is the final decoding path with respect to the received signal r. It can be seen that the decoded data is the same as the input D.sub.IN of the encoder. However, the data D.sub.IN input to the general encoder is a bit stream having a substantially infinite length. In this case, if the above-described decoding is performed with respect to the total of the encoded data, the substantially infinite time delays occur. Thus, continuous encoding is performed in the encoder, while the input data is truncated into predetermined length data in the decoder and the truncated data is decoded. The predetermined decoding length is called a decoding depth or a truncation depth. In case of FIG. 2, the length from the initial step to the fifth is the decoding depth. When decoded in such a manner, only one survival path is not left, but one survival path is left for each node at the last step. Therefore, at the last step, the Hamming distance is compared with respect to the survival path of each node, and then the path having the shortest Hamming distance is determined as the final decoding path.
The decoding with respect to one decoding depth can be divided into two methods according as how the initial state at the time of starting the decoding is established. The first method is that the initial state of the decoding depth is made to become the last state of the final decoding path of the previous decoding depth. In this case, the previous decoding information can be used as it is, but if the previous decoding path is wrong, the decoding of the decoding depth data to be decoded can be wrong. Also, this method should store the last state of the previous final decoding path. The second method does not store the last state of the previous final decoding path, but starts at all the states at the same time. In this case, since the previous decoding information is not used at all, an independent decoding can be performed at each step even if the previous decoding path was wrong. However, when the previous decoding path is correct, the possibility of selecting the wrong decoding path becomes higher than the other method.